<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Articulation Points Graph Algorithm tarjan</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="articulation-points-graph-algorithm-tarjan">Articulation Points Graph Algorithm tarjan</h1>
<p>Articulation Points 就是关键点，如果从图中移除关键点，图就会被分裂成2部分。</p>
<p>如何寻找这些点？</p>
<ol>
<li>笨办法就是遍历所有顶点，挨个尝试移除， 如果移除后，图被分成了两部分。那么就是关键点。(通过dfs或者disjoint set)</li>
<li>tarjan 算法。</li>
</ol>
<h1 id="1-tarjan算法">1. tarjan算法</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=2kREIkF9UAs&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=13">https://www.youtube.com/watch?v=2kREIkF9UAs&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=13</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/ArticulationPoint.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/ArticulationPoint.java</a></li>
</ul>
<p><img src="file:///e:\gitee\leetcode\graph\pics\tarjan.png" alt="tarjan.png"></p>
<p>注意，起始的root 点必须至少有2条边才行。</p>
<p>核心代码</p>
<pre><code class="language-java"><div><span class="hljs-keyword">for</span>(Vertex&lt;T&gt; adj : vertex.getAdjacentVertexes()){
            <span class="hljs-comment">//if adj is same as parent then just ignore this vertex.</span>
            <span class="hljs-keyword">if</span>(adj.equals(parent.get(vertex))) {
                <span class="hljs-keyword">continue</span>;
            }
            <span class="hljs-comment">//if adj has not been visited then visit it.</span>
            <span class="hljs-keyword">if</span>(!visited.contains(adj)) {
                parent.put(adj, vertex);
                childCount++;
                DFS(visited, articulationPoints, adj, visitedTime, lowTime, parent);

                <span class="hljs-keyword">if</span>(visitedTime.get(vertex) &lt;= lowTime.get(adj)) {
                    isArticulationPoint = <span class="hljs-keyword">true</span>;
                } <span class="hljs-keyword">else</span> {
                    <span class="hljs-comment">//below operation basically does lowTime[vertex] = min(lowTime[vertex], lowTime[adj]);</span>
                    lowTime.compute(vertex, (currentVertex, time) -&gt;
                        Math.min(time, lowTime.get(adj))
                    );
                }

            } <span class="hljs-keyword">else</span> { <span class="hljs-comment">//if adj is already visited see if you can get better low time.</span>
                <span class="hljs-comment">//below operation basically does lowTime[vertex] = min(lowTime[vertex], visitedTime[adj]);</span>
                lowTime.compute(vertex, (currentVertex, time) -&gt;
                                Math.min(time, visitedTime.get(adj))
                );
            }
        }
</div></code></pre>

    </body>
    </html>